/**
 * 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，重建出二叉树。
 *
 * Date: 2022-09-29
 * Time: 21:28
 */
public class Algorithm {
//    public int preIndex = 0; // 用来遍历 前序遍历结果的数组 的下标
//
//    public TreeNode reConstructBinaryTree(ArrayList<Integer> pre,ArrayList<Integer> vin) {
//        if(pre.size() == 0) { return null; }
//
//        return reConstructBinaryTreeChild(pre,vin,0,vin.size()-1);
//    }
//
//    private TreeNode reConstructBinaryTreeChild(ArrayList<Integer> pre,
//                                                ArrayList<Integer> vin,int begin, int end) {
//
//        if(begin > end) { return null; }
//
//        TreeNode root = new TreeNode(pre.get(preIndex)); // 创建头节点.
//
//        // 要先在中序遍历的数组中找到当前头节点的下标,因为
//        // 该下标的左边的数据是当前根节点的左子树,右边的数据是根节点的右子树
//
//        // 找该根节点在中序遍历数组中的下标
//        int leftRoot = findIndex(vin, pre.get(preIndex), begin, end);
//        preIndex++; // 前序遍历数组下标++
//
//        // 构建当前根节点的左子树.
//        root.left = reConstructBinaryTreeChild(pre, vin, begin,leftRoot-1);
//
//        // 构建右子树
//        root.right = reConstructBinaryTreeChild(pre, vin, leftRoot+1, end);
//
//        // 构建完毕 返回根节点
//        return root;
//    }
//    private int findIndex(ArrayList<Integer> vin, int val, int begin, int end) {
//        for(int i = begin; i <= end; ++i) {
//            if(vin.get(i) == val) {
//                return i;
//            }
//        }
//        return -1;
//    }
}
